%CHAPTER 2
\chapter{Physical simulations based on cell networks}
\label{chap:PhysicalSimulation}
This chapter presents a brief description about PickCell, a tool allowing to generate cell networks of physical systems. Their structures thus will be described in the second section as well. We next propose a methodology to develop physical simulations in term of the cell networks. Lastly, some cases are examined to demonstrate the use of the proposed methodology.
\section{PickCell tool and cell networks}
\subsection{PickCell tool}
PickCell is a modeling tool, has developed in Lab-STICC in recent years (more in document \cite{NetGenDoc}). It enables to access geographic data from various public resources as input data, namely GoogleMap, OpenStreetMap, or even picture files. The tool uses these data to analyze, process, and generate cell network structures of physical processes.\\
The main feature of the tool is extracting visible properties (potential physical systems) on geographic data such as river, forest, or road system. A process start from input data. The final results are a set of separated physical systems being represented by a group of cell networks, presented in Section~\ref{section.cellnetwork}. Generally, this process is performed throughout three main steps:
\begin{itemize}
\item \textbf{Preprocessing data:} Geographic data are usually yet well presented, especially in the case of satellite and air images. At this step, the tool increases the contrast of the data to serve the following steps.
\item \textbf{Segmenting data into cells:} In order to achieve interest regions on the data such as rivers, or roads. The data are divided into small cells. Their sizes (x, y) depend on the objective on the desirable models. In which, x and y parameter represent the \textit{width} and the \textit{height} of cells, respectively. It makes sense that with the same size of input data, if x and y values are small, the number of cells will large or vice versa.
\item \textbf{Recognizing similar cells and grouping into layers:} Typically, the tool uses 3 standard components of color (Red-Green-Blue) to classify divided cells into defined layers. Each contains a set of cells with similar colors. Next, the relations between these cells in the same layer will be defined depending on a certain CA pattern. As a result, for each layer, we have a set of cells organized as a network due to their relations (or links). These sets are considered as cell networks. The details of cell networks will be presented in the next section.
\end{itemize}
\subsection{Cell network}
\label{section.cellnetwork}
As mentioned previous, a cell network is a group of cells and the relations between them. Each typically has its data consisting of four elements: \textbf{identity}, \textbf{local state} (such as pollution density, insect population, geographic positions), \textbf{links to other cells} (or its neighbour), and \textbf{relative positions to its the neighbour}. The last one means that a cell is capable of determining the directions of its neighbour, which can be located at the eastern, the western, the northern, or the southern. This property can be useful in various situations such as simulating the weather, or flow of the fluid. For the sake of simplicity, it can be organized as pairs of number, shown in Table~\ref{table:Direction}.\\
\begin{comment}
Although the number of neighbour of each cell depend on the chosen CA, this number can be different from each other due to its position in the physical processes. For instance, Figure~\ref{img:cellnetwork1} shows that the cells are next to the riverbanks have less neighbour than other cells. 
\end{comment}
\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|}
\hline 
 \textbf{Direction} & \textbf{Value} \\ 
\hline 
East & (1,0) \\ 
\hline 
West & (-1,0) \\ 
\hline 
North & (0,-1) \\ 
\hline 
South & (0,1) \\ 
\hline 
\end{tabular} 
\caption{A proposed organization of directions in a cell network.}
\label{table:Direction} 
\end{center}
\end{table}
Table~\ref{table:Direction} formally shows an example of a cell network, which is generated from PickCell tool except for its data represented by the column named \textit{"Pollution Density"}. The data can be loaded at the beginning of simulations or at runtime.
\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|c|l|l|}\hline
 \textbf{Cell} 	& \textbf{Id}	& \textbf{Pollution Density} & \textbf{Neighbour Id} 		 & \textbf{Directions}     	\\\hline
1		& 0				    & 100      			& 590, 25, 1, 600     &  (-1,0), (1,0), (0,-1), (0,1)       \\\hline
2		& 1					& 50      			& 589, 0      		  &  (-1,0), (0,1) 	\\\hline
...		& ...				& ...      			& ...	      		  &  ...           	\\\hline
26		& 25		            	& 10       			& 0, 26      		  &  (-1,0), (0,1) 	\\\hline
...		& ...				& ...      			& ...      		  	  &  ...        		\\\hline
591		& 590		            	& 50       			& 2, 0, 589      		  &  (-1,0), (1,0), (0-1) 	\\\hline
...		& ...				& ...      			& ...      		  	  &  ...        		\\\hline
601		& 600				& 78					& 0					  &  (1,0) 	 		\\\hline
\end{tabular}
\caption{The table presents a cell network structure of 601 cells generated by PickCell tool (Von Neumann 1 CA).}
\label{table:CellNetworkStructure} 
\end{center}
\end{table}
The use of the cell network brings some advantages in developing physical simulations. Firstly, each cell network is a clear and consistent structure. All cells come from a certain physical system. They own the same type local data and have the same behaviour. This structure looks like a class in OOP (Object Oriented Programming) and its cells are objects being instantiated from that class. Under the view of software engineering, it thus especially useful in maintaining the systems. It is simple to add necessary properties to states or transitions of the models.\\
Secondly, cell networks generated from PickCell tool help to tackle the latency of input data. Many phenomena simulations have used raster data as the input for their models. It is often difficult to distinguish the interest regions with this type of data. The limitation causes the useless computations occurring on the outside of those regions. For example, in \cite{Cirbus_cellularautomata}, data cells are not belonging to the real interest area (rivers) will be marked "NoData" in the preprocessing step. The use of models built from cell networks will avoid this useless processing in default.\\
In addition to the cell network structure, the PickCell tool also allows to extract visible data. This is useful for displaying and analyzing simulated results. Figure~\ref{img:cellnetwork1} demonstrates how a river system is displayed from extracted visual data. In current version, the tool enables to generate two dimension data in the format of two concurrent programming languages, Cuda and Occam~\cite{CudaHomePage},~\cite{OccamIntroduction}. The third dimension data for elevation will appear soon in the next version.
\begin{figure}[H]
	\begin{center} 
		 \includegraphics[height=7cm]{img/cellnetwork1.png}
		 \caption{A cell network of a river system generated from PickCell tool with Von Neumann 1.}
		 \label{img:cellnetwork1}
	\end{center}
\end{figure}
In short, cell networks generated from PickCell tool are presented as skeletons for simulation models. In order to obtain a complete model by this approach, two other components need to be considered: \textit{input data} and \textit{transition rules}. These will be presented in the next section.
%-------------------------------------------------------------------------------------------------
\section{Physical simulations based on cell networks}
\label{section.SimulationSystem}
The cell network structure early presented is one of main components for this methodology. Each model has at least three other components: \textbf{cell network, input data,} and \textbf{transition rule}. The first one will be generated from geographic data with the facilitation of PickCell tool. Whereas, the two others will be defined according to the characteristics of physical systems.\\
A summary of the methodology is depicted in Figure~\ref{img:OverviewProcess}. The process has three main steps. Initially, it begins with geographic data. These data are next processed to generate a cell network by the PickCell tool. The cell network is associated with \textbf{input data} and \textbf{transition rule} to make up a complete model. Lastly, this model is executed by a simulator. \\
Currently, the cell networks are generated in two versions, Cuda and Occam codes. Cuda was chosen in this work due to adequation of its model. 
\begin{figure}[H]
			\begin{center}
		 		\includegraphics[width=10cm]{img/OverviewProcess.png}
		 		\caption{A summary of the proposed process which is used to conduct physical simulations.}
		 		\label{img:OverviewProcess}
			\end{center}
\end{figure}
\section{Case study and applications}
\label{section:CaseStudy}
This section describes a case study that has been applied to study region. It is a small area located in Mekong Delta of Vietnam, as shown in Figure~\ref{img:UMinhThuong}. In which, there are totally three physical systems: \textbf{river, forest}, and \textbf{road}. The first two of those, \textbf{river system} and \textbf{forest system}, which were considered in this project.\\
Considering applications of the proposed approach, there are two models will be conducted from the study region. One is the model of forest fire spread. The other is river pollution diffusion. In addition, we assume that a Wireless sensor network (WSN) is used to monitor the status of the forest. Thus, a model of WSN is also developed. Details of three models are later described in this section.\\
Another assumption is that there are communications between those three systems. One happens as the fire spreading close to the river. Then, ashes of the fire will pollute to the river. Meanwhile, as the sensors of the WSN recognised the fire appearing near to them, these sensors will raise emergency signals. This scene will be clarified and used as an application for a solution presented in Chapter~\ref{chap:DistributedSimulation}.
\begin{figure}[H]
			\begin{center}
		 		\includegraphics[height=8cm]{img/UMinhThuong.png}
		 		\caption{The study region: A small area in Mekong Delta, the South of Vietnam. (data source: OpenStreetMap \cite{StudyRegion})}
		 		\label{img:UMinhThuong}
			\end{center}
\end{figure}
In reality, there are many elements of \textbf{input data} will be used for models and \textbf{transition rules} are often very complicated. The goal is to create simulations as real as possible. However, in our case, some basic characteristics will be picked to express the possibility of the proposed methodology. Particularly, the \textbf{input data} and the \textbf{transition rule} of each model are presented as follows:
\subsection{The diffusion of pollution in the river}
\label{section:PollutionDiffusion}
This model is used to simulate the diffusion of pollution in a river. Regarding the context of pollution, it is possible to think of various potential situations such as chemical, oil, contaminant. Then, the diffusion much depends on the density. Thus, the pollution density was kept as input data for this model. Each cell contains an amount of pollution density, which represents the cell state. The states are changed according to the transition rule. 
\begin{itemize}
	\item{Input data:} {Pollution density.}	
	\item{Transition rule:} {At every time step, to achieve a new state at time t+1, each cell will perform sequential tasks:}
 	\begin{itemize}
 		\item If the local density value is larger than zero, it will be randomly subtracted a certain amount of its density. That proportion will be equally transported to its neighbour. %That depends on the wind direction which it holds.
 		%\item The local density is randomly reduced a little due to the loss of the liquid.
 		\item Next, it will receive some proportions from its neighbour.
 		\item Finally, the addition and the subtraction will be updated to prepare for the next step (time+1).
 	\end{itemize}
\end{itemize}
\subsection{The fire spread in the forest} 
A model used for simulating the fire spread in the forest. It is reproduced from a sample in CORMAS~\cite{cormas}. Each cell has four possible states: \textit{tree, fire, ash}, and \textit{empty}. At the beginning, some cells are initialized with the state \textit{fire}, while others are \textit{tree}. 
\begin{itemize}
	\item{Input data:} {Tree, fire, ash, and empty.}
	\item{Transition rule:}
 	\begin{itemize}
 		\item If a cell is \textit{tree} at time t, it will become \textit{fire} at time t+1 in the case that there is at least one of its neighbour is \textit{fire}.
 		\item If a cell is \textit{fire} at time t, it will become \textit{ash} at time t+1.
 		\item If a cell is \textit{ash} at time t, it will become \textit{empty} at time t+1.
 	\end{itemize}
\end{itemize}
\subsection{Wireless sensor network (WSN)}
In this study, WSN plays as a sensing component role. It regularly collect raw data from the environment, processes that data, and raises emergency alert in the case of the fire detected. A WSN will monitor status of the forest. To do that, a set of sensors will be deployed in the forest border because our consideration is the spread of the fire to other systems. In this case, we give a simple way using a distributed algorithm for the deployment of sensors. The algorithm will be described in Section~\ref{RoutingAlgorithm}. A simple WSN is achieved as shown in Figure~\ref{img:DeployingSensor}.
\begin{figure}[H]
			\begin{center}
		 		\includegraphics[height=8cm]{img/DeployingSensor.png}
		 		\caption{Deploying sensors along the forest border extracted from the study region with the 4 neighbour pattern. The communication range and the sensing range are 25 and 5 cells units, respectively.}
		 		\label{img:DeployingSensor}
			\end{center}
\end{figure}
Typically, sensors have two types of ranges. One is to indicate the sensing capacity of the sensor. This sensing range can be small. Meanwhile, the other, communication range, can be longer due to radio link technology. Thus, as deploying sensors, it is necessary to make sure that sensors are connected together depending on the value of the communication ranges.
\begin{comment}
At first, we assume that each node (cell) in the cell network has a route table, as shown in Section~\ref{RoutingAlgorithm}). 
The idea is that randomly starting from a node, at which the first sensor is established. The next position for the second sensor will be picked according the defined communication range and values in the first route table. In that route table, there is a set of nodes having a distance from them to the first node equal to the communication range. Then, one node is randomly chosen from that set to deploy the second sensor. This task will repeated on the position of the second sensor until last node reached. A simple WSN is achieved as shown in Figure~\ref{img:DeployingSensor}.
\end{comment}
\begin{itemize}
	\item{Input data:} {Sensing data.}
	\item{Transition rule:} {At every step, the nodes check data received from the fire forest simulation. In case of fire detected at some points, signals will be raised.}
\end{itemize}
\section{Routing algorithm}
\label{RoutingAlgorithm}
This section presents a routing algorithm implemented in parallel. Taking advantage of the GPU computation, a new version of this algorithm was implemented in Cuda starting from a Occam program. The routing table which can be used for deploying sensors as described in previous.\\
We assume that the network has the shape and structure like the cell network as introduced in Section~\ref{section.cellnetwork}. Generally, it consists of n nodes, numbered 0 to n-1, they are viewed as their \textit{identity}, as showed in Figure~\ref{img:RoutingNetwork}. Associating to each node is two elements: \textit{route table} and \textit{temperate table}. In which, \textit{route table} will store identities of itself and other nodes, to which it has reached after t step. The structure of this table is presented in Table~\ref{table:RouteTable}. Meanwhile, \textit{temperate table} will only contains new nodes' \textit{identity}, to which it reached at each step. It means that after each step, the values held by \textit{temperate table} are completely replaced by the new ones while the \textit{route table} can be added more new records or will be unchanged.\\
At each step, each node performs two main tasks that are sending out local \textit{temperate tables} to its neighbor and receiving \textit{temperate tables} from them as well. These tasks will be performed n-1 times. This is to assume that the maximum distance will be obtained. The algorithm is presented as the following:\\

\textbf{Algorithm in parallel:}
\begin{itemize}
	\item{Initializing}
	\begin{itemize}
		\item{Adding node's \textit{id} to local \textit{temperate table} and \textit{route table} with distance is \textit{zero}, \textit{link index} is -1.}		
	\end{itemize}	
	\item{For i to n}
	\begin{itemize}			
		\item{For each neighbour}
		\begin{itemize}
			\item{Sending local \textit{temperate table} to neighbour.}	
			\item{Receiving a \textit{temperate table} from the neighbor.}
			\item{Emptying local \textit{temperate table}}
			\item{For each \textit{id} in received \textit{temperate table}}
			\begin{itemize}
				\item{If \textit{id} does not exist in the \textit{route table}.}
				\item{Adding \textit{id}, \textit{i} as distance, and a \textit{link index} to \textit{route table}.}
				\item{Adding \textit{id} to local \textit{temperate table}.}				
			\end{itemize}
		\end{itemize}
	\end{itemize}	
\end{itemize}

%-------------Comment----------------
\begin{comment}
\begin{itemize}
	\item[]{Algorithm in parallel:}
\begin{itemize}
	\item{Initializing}
	\begin{itemize}
		\item{The id of each node is added to its \textit{temperate table}.}
	\end{itemize}
	\item{Loop from 0 to n-1}
	\begin{itemize}
		\item{Sending out message including the values of \textit{temperate table} to its neighbor.}
		\item{Receiving message from its neighbor.}
		\item{Emptying \textit{temperate table}.}
		\item{Updating \textit{route table} and \textit{temperate table}, to both which unknown identities of received messages are added. In addition, the distances for unknown identities are equal to value of the current step.}
	\end{itemize}
\end{itemize}
\end{itemize}
\end{comment}
%-------------End Comment----------------
\begin{figure}[H]
	\begin{center}
		 \includegraphics[width=4cm]{img/RoutingNetwork.png}
		 \caption{A simple network.}
		 \label{img:RoutingNetwork}
	\end{center} 
\end{figure}

\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hhline{---~---}
\multicolumn{3}{|c|}{\textbf{Node 0}} & & \multicolumn{3}{c|}{\textbf{Node 1}}\\
\hhline{---~---}
\textbf{Known Id} & \textbf{Distance} & \textbf{Links} & & \textbf{Known Id} & \textbf{Distance} & \textbf{Links}\\ 
\hhline{---~---}
0 & 0 & -1 & & 1 & 0 & -1 \\ 
\hhline{---~---}
1 & 1 & 0 & & 0 & 1 & 0 \\ 
\hhline{---~---}
3 & 1 & 1 & & 3 & 1 & 1 \\ 
\hhline{---~---}
2 & 2 & 0 & & 2 & 2 & 0 \\ 
\hhline{---~---}
\end{tabular} 
\begin{tabular}{|c|c|c|c|c|c|c|}
\hhline{---~---}
\multicolumn{3}{|c|}{\textbf{Node 2}} & & \multicolumn{3}{c|}{\textbf{Node 3}}\\
\hhline{---~---}
\textbf{Known Id} & \textbf{Distance} & \textbf{Links} & & \textbf{Known Id} & \textbf{Distance} & \textbf{Links}\\ 
\hhline{---~---}
2 & 0 & -1 & & 3 & 0 & -1 \\ 
\hhline{---~---}
3 & 1 & 0 & & 1 & 1 & 0 \\ 
\hhline{---~---}
0 & 2 & 0 & & 0 & 1 & 1 \\ 
\hhline{---~---}
1 & 2 & 1 & & 2 & 1 & 2 \\ 
\hhline{---~---}
\end{tabular} 

\caption{An example of route table at node 0 after 3 steps.}
\label{table:RouteTable} 
\end{center}
\end{table}
These tables show information held by nodes in the network. Each node can know "who" it can reach and the distance to destinations.that it can achieved. 
\section{Remarks}
The chapter presented a variety of subjects. The most noticeable is the concept of cell network. It plays an important role in developing physical models. For the next chapter, parallel computations will be employed to simulate these models.